package leetcode.dfs;

/**
 * @author : zx
 * @version V1.0
 */
public class PuKe {

    // 最小出牌次数
    public static int min = Integer.MAX_VALUE;

    /**
     * @param nums 牌库数组
     * @param count 出牌次数
     *
     */
    public static void dfs(int[] nums, int count) {
        // 如果count大于min则无需继续递归
        if (count >= min){
            return;
        }
        // 判断牌是否出尽
        boolean flag = false;
        for (int i= 0; i < nums.length; i++){
            if (nums[i] > 0) {
                flag = true;
                break;
            }
        }
        // 未出净
        if (flag){
            int i = 0;
            while (nums[i] == 0){
                i++;
            }
            // 出三对
            if (i <= nums.length-3){
                if (nums[i]>1 && nums[i+1]>1 && nums[i+2]>1){
                    for (int j = i; j < i+3; j++){
                        nums[j]-=2;
                    }
                    dfs(nums, count+1);
                    for (int j = i; j < i+3; j++){
                        nums[j]+=2;
                    }
                }
            }
            // 出5连 防止数组越界
            if (i <= nums.length-5){
                if (nums[i]>0 && nums[i+1]>0 && nums[i+2]>0 && nums[i+3]>0 && nums[i+4]>0){
                    for (int j = i; j < i+5; j++){
                        nums[j]--;
                    }
                    dfs(nums, count+1);
                    for (int j = i; j < i+5; j++){
                        nums[j]++;
                    }
                }
            }
            // 出对子
            if (nums[i] > 1){
                nums[i] -= 2;
                dfs(nums, count+1);
                nums[i] += 2;
            }
            // 出单牌
            if (nums[i] > 0){
                nums[i]--;
                dfs(nums, count+1);
                // 回溯
                nums[i]++;
            }
        }
        // 出尽
        else {
            if (count < min){
                min = count;
            }
        }



    }

    public static void main(String[] args) {
        int[] nums = new int[]{2, 2, 2, 2, 2, 0, 0, 0, 0, 0};
        dfs(nums, 0);
        System.out.println(min);
    }
}
